P6585 中子衰变 题解

我们对$n$的奇偶进行分类讨论：

若$n$是偶数，我们选择后手。对于对手每次操作，我们操作其对称的位置，将其转变为与对手操作相同的粒子。容易证得这样的操作一定合法。

若$n$是奇数，我们可以尝试先操作最中间的位置，然后使用和上面类似的对称策略。但是由于如果全部中子最后变成了同种粒子，那么后手获胜。这条规则，这个策略并不成立。

换一个思路，我们选择后手。我们的操作策略要保证，每次我方操作后，局面状态满足一个循环不变式：

存在一个$m\le\frac{n-1}{2}$使得，前$m$个粒子和后$m$个粒子相反对称，且中间剩余的一段除某一个端点没被操作外，其他部分都被操作成了相同的粒子。其中，相反对称的定义是：对于任意$i\le m$，左起第$i$个粒子和右起第$i$个粒子要么都没被操作过，要么电性相反。

例如，以下情况都是满足条件的：

（三个例子中$m$分别可以取$4,3,0$）

注意初始状态也是满足这个条件的，$m$取$\frac{n-1}{2}$即可。

我们可以采取以下策略维护这个循环不变式：

选择后手，对于对手每次操作，我们都操作其对称的位置，将其转变为与对手操作相反的粒子。但是有两种例外情况，可能导致我们的操作不合法：

• 对手操作了中间一段剩下的那个端点。（例如在上面的第二行例子中，对手将第六格变成$1$）。由于我们保证左右两侧是相反对称的，那么与中间一段相邻的两个粒子中，必然有一个是可操作的。我们把这个格子操作成和中间一段相同的粒子（接上面的例子，把第七格变成$1$），易发现这样操作后循环不变式仍然满足，且$m$的值减少了$1$。特殊地，如果$m$已经是$0$，对手这样操作后必然导致所有粒子相同，根据规则后手胜。

• 对手操作了中间一段剩下的那个端点相邻的一个点，且与中段的电性相同（例如在上面的第二行例子中，对手将第七格变成$1$）。此时我们只需要把那个端点操作成相同的粒子即可（接上面的例子，把第六格变成$1$）。循环不变式仍然成立，且$m$的值减少了$1$。

如果我们一直维护了这个循环不变式，对于对手的每一个合法操作我们都有一个对应的合法操作，显然后手必胜。